package cc.wsyw126.java.lintCode;

import cc.wsyw126.java.lintCode.convert_binary_search_tree_to_doubly_linked_list.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * Created by Administrator on 2017/4/13.
 */
public class FindPathEqualsSum {
    private int sum = 0;
    private LinkedList<TreeNode> list = new LinkedList<>();
    private ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    private int value = 0;

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        value = target;
        if (root!=null) {
            doFindPath(root);
        }
        return result;
    }

    private void doFindPath(TreeNode root) {
        TreeNode temp = root;
        list.add(temp);
        sum += temp.val;

        if (temp.right == null && temp.left == null) {
            if (sum == value) {
                ArrayList<Integer> integers = new ArrayList<>();
                for (TreeNode treeNode : list) {
                    integers.add(treeNode.val);
                }
                result.add(integers);
            }
            sum -= temp.val;
            list.removeLast();
            return;
        }
        if (temp.left != null) {
            doFindPath(temp.left);

        }
        if (temp.right != null) {
            doFindPath(temp.right);

        }
        sum -= temp.val;
        list.removeLast();
        return;
    }

    public static void main(String[] args) {
        FindPathEqualsSum findPathEqualsSum = new FindPathEqualsSum();
        TreeNode root = new TreeNode(10);
        TreeNode l = new TreeNode(5);
        TreeNode r = new TreeNode(12);
        TreeNode ll = new TreeNode(4);
        TreeNode lr = new TreeNode(7);
        root.left = l;
        root.right=r;
        l.left=ll;
        l.right=lr;
        ArrayList<ArrayList<Integer>> arrayLists = findPathEqualsSum.FindPath(root, 22);
        for (ArrayList<Integer> arrayList : arrayLists) {
            for (Integer integer : arrayList) {
                System.out.print(integer + "\t");
            }
            System.out.println();
        }

    }
}
